Mi manual de algoritmos/version_maraton_interuniversitaria_2008-2/src/number_theory/criba.cpp

   1 #include <iostream>
   2
   3 const int SIZE = 1000000;
   4
   5 //criba[i] = false si i es primo
   6 bool criba[SIZE+1];
   7
   8 void buildCriba(){
   9   memset(criba, false, sizeof(criba));
  10
  11   criba[0] = criba[1] = true;
  12   for (int i=2; i<=SIZE; i += 2){
  13     criba[i] = true;
  14   }
  15
  16   for (int i=3; i<=SIZE; i += 2){
  17     if (!criba[i]){
  18       for (int j=i+i; j<=SIZE; j += i){
  19         criba[j] = true;
  20       }
  21     }
  22   }
  23 }